|
In graph theory, the Lovász number of a graph is a real number that is an upper bound on the Shannon capacity of the graph. It is also known as Lovász theta function and is commonly denoted by ϑ(''G''). This quantity was first introduced by László Lovász in his 1979 paper ''On the Shannon Capacity of a Graph''.〔.〕 == Definition == Let ''G'' = (''V'', ''E'') be a graph on ''n'' vertices. An ordered set of ''n'' unit vectors ''U'' = (''u''''i'' | ''i'' ∈ ''V'') ⊂ R''N'' is called an orthonormal representation of ''G'' in R''N'', if ''u''''i'' and ''u''''j'' are orthogonal whenever vertices ''i'' and ''j'' are ''not'' adjacent in ''G'': : Clearly, every graph admits an orthonormal representation with ''N'' = ''n'' (just represent vertices by distinct vectors from the standard basis of R''n''), but in general it might be possible to take ''N'' considerably smaller than the number of vertices ''n''. The Lovász number ϑ of graph ''G'' is defined as follows: : where ''c'' is a unit vector in R''N'' and ''U'' is an orthonormal representation of ''G'' in R''N''. Here minimization implicitly is performed also over the dimension ''N'', however without loss of generality it suffices to consider ''N'' = ''n''.〔If ''N'' > ''n'' then one can always achieve a smaller objective value by restricting ''c'' to the subspace spanned by vectors ''u''''i'' which is at most ''n''-dimensional.〕 Intuitively, this corresponds to minimizing the half-angle of a rotational cone containing all representing vectors of an orthonormal representation of ''G''. If the optimal angle is ϕ, then ϑ(''G'') = 1/cos2(ϕ) and ''c'' corresponds to the symmetry axis of the cone.〔See Proposition 5.1 in , pp. 28.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lovász number」の詳細全文を読む スポンサード リンク
|